package recursion;


import java.util.HashMap;
import java.util.Map;

public class RecursionTest {

    private static Map<Integer, Long> s_mapResult = new HashMap<>();

    public static void main(String[] args) {
        int a = 40;
        long iStartTime = System.currentTimeMillis();
        System.out.println(mountStairs(a));
        System.out.println(System.currentTimeMillis() - iStartTime);
    }


    /**
     * 假如这里有 n 个台阶，每每次你可以跨 1 个台阶或者 2 个台阶, 请问走这 n 个台阶有多少种走法？
     * 推出公式：f(n) = f(n - 1) + f(n - 2)
     * 终止条件：f(1) = 1, f(2) = 2
     * 转换代码
     */
    private static long mountStairs(int iCount) {

        if (iCount == 1) {
            return 1;
        }

        if (iCount == 2) {
            return 2;
        }

        //若不存在结果缓存，则 40 层台阶计算耗时 500 毫秒左右, 使用了缓存 1 毫秒
        if (s_mapResult.containsKey(iCount)) {
            return s_mapResult.get(iCount);
        }

        long iResult = mountStairs(iCount - 1) + mountStairs(iCount - 2);
        if (!s_mapResult.containsKey(iCount)) {
            s_mapResult.put(iCount, iResult);
        }

        return iResult;
    }

}
